#pragma once

template<class K>
struct Hash {
	size_t operator()(const K& key) {
		return key;
	}
};
template<>
struct Hash<string> {
	size_t operator()(const string& s) {
		size_t value = 0;
		for (auto e : s) {
			value *= 31;
			value += e;
		}
		return value;
	}
};

namespace closeHash {
	enum State {
		EXIST,
		DELETE,
		EMPTY
	};
	template<class K,class V>
	struct HashData {
		pair<K, V> _kv;
		State _state = EMPTY;
	};
	template<class K,class V,class HashFunc = Hash<K>>
	class HashTable {
	public:
		bool Erase(const K& key) {
			HashData<K, V>* ret = Find(key);
			if (ret == nullptr)
				return false;
			else {
				_n--;
				ret->_state = DELETE;
				return true;
			}
		}
		HashData<K, V>* Find(const K& key) {
			if (_table.size() == 0)
				return nullptr;
			HashFunc hf;
			size_t start = hf(key) % _table.size();
			size_t i = 0;
			size_t index = start;
			while (_table[index]._state != EMPTY) {
				if (_table[index]._kv.first == key && _table[index]._state == EXIST)
					return &_table[index];
				i++;
				index = start + i;
				index %= _table.size();
			}
			return nullptr;
		}
		bool Insert(const pair<K, V>& kv) {
			HashData<K, V>* ret = Find(kv.first);
			if (ret)
				return false;
			if (_table.size() == 0 || _n * 10 / _table.size() > 7) {
				//扩容
				size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;
				HashTable<K, V> newTable;
				newTable._table.resize(newSize);
				for (size_t i = 0; i < _table.size(); i++) {
					if (_table[i]._state == EXIST)
						newTable.Insert(_table[i]._kv);
				}
				_table.swap(newTable._table);
			}
			HashFunc hf;
			size_t start = hf(kv.first) % _table.size();
			size_t i = 0;
			size_t index = start;
			while (_table[index]._state != EMPTY) {
				i++;
				index = start + i;
				index %= _table.size();
			}
			_table[index]._kv = kv;
			_table[index]._state = EXIST;
			_n++;
			return true;
		}
	private:
		vector<HashData<K, V>> _table;
		size_t _n;
	};
	void test() {
		HashTable<int, int> ht;
		int a[] = { 2,12,22,32,42,52,62 };
		for (auto& e : a) {
			ht.Insert(make_pair(e, e));
		}
		ht.Insert(make_pair(72, 72));
		ht.Insert(make_pair(32, 32));
		//ht.Insert(make_pair(-1, -1));
		ht.Insert(make_pair(-999, -999));

		cout << ht.Find(12) << endl;
		ht.Erase(12);
		cout << ht.Find(12) << endl;
	}
}

namespace openHash {
	template<class T>
	struct HashNode {
		T _data;
		HashNode<T>* _next;
		HashNode(const T& data)
			:_data(data)
			,_next(nullptr)
		{}
	};

	template<class K, class T, class KeyOfT, class HashFunc>
	class HashBucket;

	template<class K,class T,class Ref, class Ptr,class KeyOfT,class HashFunc>
	struct __htIterator {
		typedef HashNode<T> Node;
		typedef __htIterator<K, T, Ref, Ptr, KeyOfT, HashFunc> self;

		Node* _node;
		HashBucket<K, T, KeyOfT, HashFunc>* _pht;

		__htIterator(Node* node,HashBucket<K,T,KeyOfT,HashFunc>* pht)
			:_node(node)
			,_pht(pht)
		{}
		Ref operator*() {
			return _node->_data;
		}
		Ptr operator->() {
			return &_node->_data;
		}
		self& operator++() {
			if (_node->_next) {
				_node = _node->_next;
			}
			else {
				KeyOfT kot;
				HashFunc hf;
				size_t index = hf(kot(_node->_data)) % _pht->_table.size();
				index++;
				//找到下一个不为空的桶
				while (index < _pht->_table.size()) {
					if (_pht->_table[index])
						break;
					else
						index++;
				}
				if (index == _pht->_table.size())
					_node = nullptr;
				else
					_node = _pht->_table[index];
			}
			return *this;
		}
		bool operator==(const self& s) const {
			return _node == s._node;
		}
		bool operator!=(const self& s) const {
			return _node != s._node;
		}
	};

	template<class K,class T,class KeyOfT,class HashFunc>
	class HashBucket {
		typedef HashNode<T> Node;

		template<class K, class T, class Ref, class Ptr, class KeyOfT, class HashFunc>
		friend struct __htIterator;

		typedef HashBucket<K, T, KeyOfT, HashFunc> self;
	public:
		typedef __htIterator<K, T, T&, T*, KeyOfT, HashFunc> iterator;

		/*HashBucket() {

		}*/

		HashBucket() = default;
		HashBucket(const self& hb) {
			_table.resize(hb._table.size());
			for (size_t i = 0; i < hb._table.size(); i++) {
				Node* cur = hb._table[i];
				while (cur) {
					Node* copy = new Node(cur->_data);
					copy->_next = _table[i];
					_table[i] = copy;

					cur = cur->_next;
				}
			}
		}

		self& operator=(self hb) {
			swap(_n, hb._n);
			_table.swap(hb._table);
			return *this;
		}
		~HashBucket() {
			for (size_t i = 0; i < _table.size(); i++) {
				Node* cur = _table[i];
				while (cur) {
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_table[i] = nullptr;
			}
		}
		iterator begin() {
			for (size_t i = 0; i < _table.size(); i++) {
				if (_table[i])
					return iterator(_table[i], this);
			}
			return end();
		}
		iterator end() {
			return iterator(nullptr, this);
		}
		bool Erase(const K& key) {
			if (_table.empty())
				return false;
			HashFunc hf;
			size_t index = hf(key) % _table.size();
			Node* cur = _table[index];
			Node* prev = nullptr;
			KeyOfT kot;
			while (cur) {
				if (kot(cur->_data) == key) {
					if (prev == nullptr)
						_table[index] = cur->_next;
					else
						prev->_next = cur->_next;
					delete cur;
					_n--;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}
		iterator Find(const K& key) {
			if (_table.empty())
				return end();
			HashFunc hf;
			size_t index = hf(key) % _table.size();
			Node* cur = _table[index];
			KeyOfT kot;
			while (cur) {
				if (kot(cur->_data) == key)
					return iterator(cur, this);
				cur = cur->_next;
			}
			return end();
		}
		pair<iterator,bool> Insert(const T& data) {
			KeyOfT kot;
			iterator ret = Find(kot(data));
			if (ret != end())
				return make_pair(ret, false);
			HashFunc hf;
			
			if (_n == _table.size()) {
				//扩容
				size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;
				vector<Node*> newBucket;
				newBucket.resize(newSize);
				for (size_t i = 0; i < _table.size(); i++) {
					Node* cur = _table[i];
					while (cur) {
						Node* next = cur->_next;
						size_t index = hf(kot(cur->_data)) % newBucket.size();
						cur->_next = newBucket[index];
						newBucket[index] = cur;

						cur = next;
					}
					_table[i] = nullptr;
				}
				_table.swap(newBucket);
			}
			
			size_t index = hf(kot(data)) % _table.size();
			Node* newNode = new Node(data);
			newNode->_next = _table[index];
			_table[index] = newNode;
			_n++;
			return make_pair(iterator(newNode, this), true);
		}
	private:
		vector<Node*> _table;
		size_t _n = 0;
	};
}